20.CS61C Lab2
Lab 2
Exercise 0: Makefiles
这个 Exercise 要求我们学会使用 Makefile 来编译 C 语言程序
题目给出了一个 makefile
UNAME_S := $(shell uname -s)
CC=gcc
LD=gcc
CFLAGS=-ggdb -Wall -std=c99
LDFLAGS=
ifeq ($(UNAME_S), Darwin)
MEMCHECK=valgrind --tool=memcheck --leak-check=full --track-origins=yes --dsymutil=yes
endif
ifeq ($(UNAME_S), Linux)
MEMCHECK=valgrind --tool=memcheck --leak-check=full --track-origins=yes
endif
BIT_OPS_OBJS = bit_ops.o test_bit_ops.o
BIT_OPS_PROG = bit_ops
LFSR_OBJS = lfsr.o test_lfsr.o
LFSR_PROG = lfsr
VECTOR_OBJS=vector.o vector-test.o
VECTOR_PROG=vector-test
BINARIES=$(VECTOR_PROG) $(BIT_OPS_PROG) $(LFSR_PROG)
all: $(BINARIES)
$(BIT_OPS_PROG): $(BIT_OPS_OBJS)
$(CC) $(CFLAGS) -g -o $(BIT_OPS_PROG) $(BIT_OPS_OBJS) $(LDFLAGS)
$(LFSR_PROG): $(LFSR_OBJS)
$(CC) $(CFLAGS) -g -o $(LFSR_PROG) $(LFSR_OBJS) $(LDFLAGS)
lfsr.c: lfsr.h
test_lfsr.c: lfsr.h
bit_ops.c: bit_ops.h
test_bit_ops.c: bit_ops.h
.c.o:
$(CC) -c $(CFLAGS) $<
vector-memcheck: $(VECTOR_PROG)
$(MEMCHECK) ./$(VECTOR_PROG)
clean:
-rm -rf core *.o *~ "#"*"#" Makefile.bak $(BINARIES) *.dSYM
vector.c: vector.h
vector-test.c: vector.h
然后给出了 10 个问题
- Which target is part of a rule that deletes all the compiled programs?
哪个目标是删除所有编译程序的规则的一部分？
clean
- Which target is part of a rule that makes all the compiled programs?
哪个目标是创建所有编译程序的规则的一部分？
all
- Which compiler is currently being used?
CC = gcc
- What C standard are we currently using?
CFLAGS = -ggdb -Wall -std=c99
- How would we reference a variable “FOO” in a makefile?
$(FOO)
- What operating system does the term “Darwin” represent?
"Darwin"代表的是 macOS（和 iOS 等苹果操作系统）的底层核心操作系统。
- What line creates the lfsr program from its object files? (Give its line number.)
$(LFSR_PROG): $(LFSR_OBJS) # 行号：假设为第 24 行
$(CC) $(CFLAGS) -g -o $@ $^ $(LDFLAGS) # 行号：第 25 行（实际编译命令）
Exercise 1: Bit Operations
编写程序完成 get_bit，set_bit，flip_bit
#include <stdio.h>
#include "bit_ops.h"
// Return the nth bit of x.
// Assume 0 <= n <= 31
unsigned get_bit(unsigned x,
unsigned n) {
// YOUR CODE HERE
return (x >> n) & 1;
// Returning -1 is a placeholder (it makes
// no sense, because get_bit only returns
// 0 or 1)
return -1;
}
// Set the nth bit of the value of x to v.
// Assume 0 <= n <= 31, and v is 0 or 1
void set_bit(unsigned * x,
unsigned n,
unsigned v) {
// YOUR CODE HERE
if (v == 1)
*x |= (1 << n);
else
*x &= ~(1 << n);
}
// Flip the nth bit of the value of x.
// Assume 0 <= n <= 31
void flip_bit(unsigned * x,
unsigned n) {
(*x) ^= (1 << n);
// YOUR CODE HERE
}
Exercise 2: Linear Feedback Shift Register
这个 Exercise 要求你实现一个线性反馈移位寄存器，这个图好像挂了
根据描述很容易
void lfsr_calculate(uint16_t *reg) {
/* YOUR CODE HERE */
int lfsr = *reg;
uint16_t bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5)) & 1;
lfsr = (lfsr >> 1) | (bit << 15);
*reg = lfsr;
}
Exercise 3: Memory Management
在本 Exercise，程序实现了一个可变数组 vector 的框架，他要求我们阅读代码并回答问题？
为什么 bad_vector_new() 是不好的？
/* Bad example of how to create a new vector */
vector_t *bad_vector_new() {
/* Create the vector and a pointer to it */
vector_t *retval, v;
retval = &v;
/* Initialize attributes 初始化 */
retval->size = 1;
retval->data = malloc(sizeof(int));
if (retval->data == NULL) {
allocation_failed();
}
retval->data[0] = 0;
return retval;
}
这里的 retval 指向了一个由栈内存的变量 v 这个变量在函数运行结束后会被自动释放掉
vector_t also_bad_vector_new() {
/* Create the vector */
vector_t v;
/* Initialize attributes */
v.size = 1;
v.data = malloc(sizeof(int));
if (v.data == NULL) {
allocation_failed();
}
v.data[0] = 0;
return v;
}
also_bad_vector_new 这段代码也不太好的原因是，v.data = malloc(sizeof(int)); 这里申请的内存在堆内存上
然后返回的时候发生了浅拷贝，如果调用者不自己手动释放内存就会导致内存泄漏
然后我们完善 vector.c 和 vector.c
/* Include the system headers we need */
#include <stdlib.h>
#include <stdio.h>
/* Include our header */
#include "vector.h"
/* Define what our struct is */
struct vector_t {
size_t size;
int *data;
};
/* Utility function to handle allocation failures. In this
case we print a message and exit. */
static void allocation_failed() {
fprintf(stderr, "Out of memory.\n");
exit(1);
}
/* Bad example of how to create a new vector */
vector_t *bad_vector_new() {
/* Create the vector and a pointer to it */
vector_t *retval, v;
retval = &v;
/* Initialize attributes 初始化 */
retval->size = 1;
retval->data = malloc(sizeof(int));
if (retval->data == NULL) {
allocation_failed();
}
retval->data[0] = 0;
return retval;
}
/* Another suboptimal way of creating a vector */
vector_t also_bad_vector_new() {
/* Create the vector */
vector_t v;
/* Initialize attributes */
v.size = 1;
v.data = malloc(sizeof(int));
if (v.data == NULL) {
allocation_failed();
}
v.data[0] = 0;
return v;
}
/* Create a new vector with a size (length) of 1
and set its single component to zero... the
RIGHT WAY */
vector_t *vector_new() {
/* Declare what this function will return */
vector_t *retval;
/* First, we need to allocate memory on the heap for the struct */
retval = malloc(sizeof (vector_t));
/* Check our return value to make sure we got memory */
if (retval == NULL) {
allocation_failed();
}
/* Now we need to initialize our data.
Since retval->data should be able to dynamically grow,
what do you need to do? */
retval->size = 1;
retval->data = malloc(sizeof(int));
/* Check the data attribute of our vector to make sure we got memory */
if (retval->data == NULL) {
free(retval); //Why is this line necessary?
allocation_failed();
}
/* Complete the initialization by setting the single component to zero */
retval->data[0] = 0;
/* and return... */
return retval;
}
/* Return the value at the specified location/component "loc" of the vector */
int vector_get(vector_t *v, size_t loc) {
/* If we are passed a NULL pointer for our vector, complain about it and exit. */
if(v == NULL) {
fprintf(stderr, "vector_get: passed a NULL vector.\n");
abort();
}
/* If the requested location is higher than we have allocated, return 0.
* Otherwise, return what is in the passed location.
*/
if (loc < v->size) {
return v->data[loc];
} else {
return 0;
}
}
/* Free up the memory allocated for the passed vector.
Remember, you need to free up ALL the memory that was allocated. */
void vector_delete(vector_t *v) {
/* YOUR SOLUTION HERE */
if (v == NULL) {
fprintf(stderr, "vector_delete: passed a NULL vector.\n");
abort();
}
/* Free the data array */
free(v->data);
}
/* Set a value in the vector. If the extra memory allocation fails, call
allocation_failed(). */
void vector_set(vector_t *v, size_t loc, int value) {
/* What do you need to do if the location is greater than the size we have
* allocated? Remember that unset locations should contain a value of 0.
*/
if (v == NULL) {
fprintf(stderr, "vector_set: passed a NULL vector.\n");
abort();
}
if (loc >= v->size) {
size_t new_size = loc + 1;
int *new_data = realloc(v->data, new_size * sizeof(int));
if (new_data == NULL) {
allocation_failed();
}
v->data = new_data;
for (size_t i = v->size; i < new_size; i++) {
v->data[i] = 0;
}
v->size = new_size;
}
v->data[loc] = value;
/* YOUR SOLUTION HERE */
}
#ifndef CS61C_VECTOR_H_
#define CS61C_VECTOR_H_
/* vector.h originally written by Jeremy Huddleston <jeremyhu@eecs.berkeley.edu> Sp2004
*
* So it looks like you've decided to venture into the "other" files of this
* lab. Good. C Header files (the .h extension) are a way of telling other .c
* files what they can have access to. You usually include stdlib.h in your
* C programs, and this process is identical to including this .h file with the
* one change being:
*
* #include "file.h"
* versus
* #include <file.h>
*
* The difference is that the <> notation is for system header files and the ""
* is for ones you provide yourself (in your local directory for instance).
*
* The header file starts off with
* #ifndef CS61C_VECTOR_H_
* #define CS61C_VECTOR_H_
*
* and ends with a final #endif. This prevents the file from being included
* more than once which could've possibly resulted in an infinite loop of
* file inclusions.
*
* First, we define the 'vector_t' datatype. This next line says that a 'vector_t'
* is the same as a 'struct vector_t'. So anywhere in the code after this, we
* can use 'vector_t *' to mean a pointer to a 'struct vector_t' (which is defined in
* vector.c). We can get away with doing this even though we don't know what a
* struct vector is because all struct pointers have the same representation in memory.
*/
#include <sys/types.h>
typedef struct vector_t vector_t;
/*
* Next, we provide the prototypes for the functions defined in vector.c. This
* is a way of telling the .c files that #include this header what they will
* have access to.
*/
/* Create a new vector */
vector_t *vector_new();
/* Free up the memory allocated for the passed vector */
/* YOUR CODE HERE */
void vector_delete(vector_t *v);
void vector_set(vector_t *v, size_t loc, int value);
/* Return the value in the vector */
int vector_get(vector_t *v, size_t loc);
/* Set a value in the vector */
/* YOUR CODE HERE */
#endif